package jzoffer;

import java.util.LinkedList;
import java.util.Stack;

/**
 * Author:   dengxin
 * Date:     2020/6/12 5:47 下午
 * 二叉树镜像
 */
@SuppressWarnings("all")
public class jz18 {

    //递归法
    private static void mirror1(TreeNode root) {
        if (root == null) {
             return;
        }
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        mirror1(root.left);
        mirror1(root.right);
    }

    //遍历法
    private static void mirror(TreeNode root) {
        if (root == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        //将根元素放入栈中
        stack.push(root);
        while (!stack.empty()) {
            //栈中有元素时，依次弹出栈中元素
            TreeNode node = stack.pop();
            if (node.left != null || node.right != null) {
                TreeNode leftNode = node.left;
                node.left = node.right;
                node.right = leftNode;
            }
            if (node.left != null) {
                stack.push(node.left);
            }
            if (node.right != null) {
                stack.push(node.right);
            }
        }

    }

    static class TreeNode {
        int value;
        TreeNode left;
        TreeNode right;

        public TreeNode(int value) {
            this.value = value;
        }
    }
}
